package com.kingwood.algorithm.test;


import java.util.*;

/**
 * @Author 22025812
 * @Description: 逻辑分析题目第二部分，这类的题太多了
 * @Date: 2024/3/4 10:52
 * @Modified By：
 * @Version 1.0
 */
public class LuojiFenxi2 {

    /**
     * 石头剪刀布游戏
     * https://fcqian.blog.csdn.net/article/details/134725034
     * @param scanner
     * @return
     */
    public static String getGameResult(Scanner scanner) {
        HashMap<Character, ArrayList<String>> cMap = new HashMap<>();
        while (scanner.hasNext()) {
            String playerName = scanner.next();
            char gestur = scanner.next().charAt(0);

            if (gestur < 'A' || gestur > 'C') {
                return "NULL";
            }

            cMap.putIfAbsent(gestur, new ArrayList<>());
            cMap.get(gestur).add(playerName);
        }

        ArrayList<String> ans;
        switch (cMap.size()){
            case 3:
            case 1:
                // 只有一种或三种手势都是平局，没有胜利的玩家
                return "NULL";
            case 2:
                // 两种手势，判断谁赢了
                if (!cMap.containsKey('A')) {
                    ans = cMap.get('B');
                } else if (!cMap.containsKey('B')) {
                    ans = cMap.get('C');
                } else {
                    ans = cMap.get('A');
                }

                ans.sort(String::compareTo);
                break;
            default:
                return "NULL";
        }

        String res = "";
        for (String s : ans) {
            res += s + " ";
        }

        return res;
    }

    public static int getMaxPeekNums(int[] arr, int strength) {
        HashSet<Integer> idx = new HashSet<>();
        climb(arr, strength, idx, true);
        reverse(arr);
        climb(arr, strength, idx, false);
        return idx.size();
    }

    public static void climb(int[] arr, int strength, HashSet<Integer> idx, boolean direction) {
        int j = 0;
        while (j < arr.length && arr[j] != 0) {
            j++;
        }

        int cost = 0;

        for (int i=j+1;i < arr.length; i++) {
            if (arr[i] == 0) {
                cost = 0;
                continue;
            }

            int diff = arr[i] - arr[i-1];
            if (diff > 0) {
                // 如果是上坡
                cost += diff * 3;
                if (i + 1 >= arr.length || arr[i] > arr[i+1]) {
                    if (cost <= strength) {
                        if (direction) {
                            idx.add(i);
                        } else {
                            idx.add(arr.length - i - 1);
                        }
                    } else {
                        break;
                    }
                }
            } else if (diff < 0) {
                // 如果是下坡
                cost -= diff * 3;
            }
        }
    }

    public static void reverse(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    /**
     * 找数字
     * https://fcqian.blog.csdn.net/article/details/134639750
     * @param n
     * @return
     */
    public static int findMinNum(int n) {
        String nBinStr = "0" + Integer.toBinaryString(n);
        char[] mBinCharArr = nBinStr.toCharArray();

        int countOne = 0;
        int len = mBinCharArr.length;
        for (int i = len - 2; i >= 0; i--) {
            if (mBinCharArr[i] == '0' && mBinCharArr[i + 1] == '1') {
                mBinCharArr[i] = '1';
                mBinCharArr[i + 1] = '0';

                if (countOne > 0) {
                    for (int j=i+2; j < len; j++) {
                        if (j < len - countOne) {
                            mBinCharArr[j] = '0';
                        } else {
                            mBinCharArr[j] = '1';
                        }
                    }
                }

                break;
            }

            if (mBinCharArr[i + 1] == '1') {
                countOne++;
            }
        }

        int m = Integer.parseInt(String.valueOf(mBinCharArr), 2);
        return m;
    }

    /**
     * 贪吃的猴子
     * https://blog.csdn.net/qfc_128220/article/details/135049306
     * @param arr
     * @param num
     * @return
     */
    public static int getMaxBananaNums(int[] arr, int num) {
        int leftSum = 0;
        int rightSum = 0;
        int len = arr.length;

        for (int i=len -num; i < len; i++) {
            rightSum += arr[i];
        }

        if (num >= len) {
            return rightSum;
        }

        int sum = leftSum + rightSum;
        int ans = sum;
        int l = 0;
        int r = len - num;

        while (l < len) {
            sum += arr[l++] + arr[r++];
            ans = Math.max(ans, sum);
        }

        return ans;
    }

    /**
     * 推荐性选择
     * @param scanner
     * @return
     */
    public static String tuiJianXuanZe(Scanner scanner) {
        int n = Integer.parseInt(scanner.nextLine()); // 窗口数量
        int k = Integer.parseInt(scanner.nextLine()); // 窗口大小

        ArrayList<LinkedList<Integer>> lists = new ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.length() == 0) {
                break;
            }

            Integer[] arr = Arrays.stream(line.split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
            lists.add(new LinkedList<>(Arrays.asList(arr)));
        }

        int[] windows = new int[n*k];
        int idx = 0; // 窗口矩阵中正在赋值的索引位置
        int level = 0; // 正在从第level个列表中取值

        while (idx < windows.length) {
            // 当前轮次是否发生了借的动作
            boolean flag = false;

            for (int i = 0; i < n; i++) {
                windows[idx++] = lists.get(level).removeFirst();
                if (lists.get(level).size() == 0 && lists.size() > 1) {
                    lists.remove(level);
                    level %= lists.size(); // 防止越界
                    flag = true; // 发生了借的动作
                }
            }

            if (!flag) {
                // 切换到下一行
                level = (level + 1) % lists.size();
            }
        }

        StringJoiner sj = new StringJoiner(" ");
        // 遍历窗口矩阵中的列
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < k; i++) {
                sj.add(String.valueOf(windows[i * n + j]));
            }
        }

        return sj.toString();
    }

    static String A;
    static String B;
    static int m;
    static int n;

    /**
     * 两个字符串间的最短路径问题
     * https://fcqian.blog.csdn.net/article/details/134759904
     * @return
     */
    public static int getMinShortPath() {
        int[][] dp = new int[m + 1][n + 1];

        for (int j=0; j<=n; j++) {
            dp[0][j] = j;
        }

        for(int i=0; i<=m; i++) {
            dp[i][0] = i;
        }

        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                if (A.charAt(j-1) == B.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }

        return dp[m][n];
    }

    public static int getMinShortPath2() {
        int[] preRow = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            preRow[j] = j;
        }

        int[] curRow = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            curRow[0] = i;
            for (int j = 1; j <= n; j++) {
               if (A.charAt(j-1) == B.charAt(i-1)) {
                    curRow[j] = preRow[j-1] + 1;
                } else {
                    curRow[j] = Math.min(preRow[j], curRow[j-1]) + 1;
                }
            }

            System.arraycopy(curRow, 0, preRow, 0, n + 1);
        }


        return curRow[n];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        System.out.println(getGameResult(scanner));
//        int[] arr = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
//        int strength = scanner.nextInt();
//        int ans = getMaxPeekNums(arr, strength);
//        System.out.println(ans);
//        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        int strength = scanner.nextInt();
//        int ans = getMaxPeekNums(arr, strength);
//        System.out.println(ans);

//        int n = scanner.nextInt();
//        System.out.println(findMinNum(n));
//
//        String a = "1234567";
//        System.out.println(a.substring(3));

//        int n = Integer.parseInt(scanner.nextLine());
//        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        int num = Integer.parseInt(scanner.nextLine());
//        System.out.println(getMaxBananaNums(arr, num));

//        System.out.println(tuiJianXuanZe(scanner));
        A = scanner.next();
        B = scanner.next();
        m = B.length();
        n = A.length();

        System.out.println(getMinShortPath());
    }
}
